This paper presents the results of an experimental study of graphpartitioning. We describe a new heuristic technique, path optimization, and itsapplication to two variations of graph partitioning: the max_cut problem andthe min_quotient_cut problem. We present the results of computationalcomparisons between this technique and the Kernighan-Lin algorithm, thesimulated annealing algorithm, the FLOW-lagorithm the multilevel algorithm, andteh recent 0.878-approximation algorithm. The experiments were conducted on twoclasses of graphs that have become standard for such tests: random and randomgeometric. They show that for both classes of inputs and both variations of theproblem, the new heuristic is competitive with the other algorithms and holdsan advantage for min_quotient_cut when applied to very large, sparse geometricgraphs. In the last part of the paper, we describe an approach to analyzinggraph partitioning algorithms from the statistical point of view. Everypartitioning of a graph is viewed as a result achieved by a "near gready"partitioning algorithm. The experiments show that for "good" partitionings, thenumber of non-greedy steps needed to obtain them is quite small; moreover, itis "statistically" smaller for better partitionings. This led us to conjecturethat there exists an "optimal" distribution of the non-greedy steps thatcharacterize the classes of graphs that we studied.
展开▼
